package com.sheng.leetcode.year2023.month09.day18;

import org.junit.Test;

/**
 * @author by ls
 * @date 2023/9/18
 * <p>
 * 337. 打家劫舍 III<p>
 * <p>
 * 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。<p>
 * 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，<p>
 * 聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。<p>
 * 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。<p>
 * <p>
 * 示例 1:<p>
 * 输入: root = [3,2,3,null,3,null,1]<p>
 * 输出: 7<p>
 * 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7<p>
 * <p>
 * 示例 2:<p>
 * 输入: root = [3,4,5,1,3,null,1]<p>
 * 输出: 9<p>
 * 解释: 小偷一晚能够盗取的最高金额 4 + 5 = 9<p>
 * <p>
 * 提示：<p>
 * 树的节点数在 [1, 10^4] 范围内<p>
 * 0 <= Node.val <= 10^4<p>
 */
public class LeetCode0337 {

    @Test
    public void test01() {
//        TreeNode root = new TreeNode(3, new TreeNode(2, null, new TreeNode(3)), new TreeNode(3, null, new TreeNode(1)));
//        TreeNode root = new TreeNode(3, new TreeNode(4, new TreeNode(1), new TreeNode(3)), new TreeNode(5, null, new TreeNode(1)));
        TreeNode root = new TreeNode(2, new TreeNode(1, null, new TreeNode(4)), new TreeNode(3));
        //      2
        //  1       3
        // numm 4  null null
        System.out.println(new Solution().rob(root));
    }
}

class Solution {

    int n = 0;

    public int rob(TreeNode root) {
        // 一层一层的搜索，但是不能连续，获取最大值
        // 可以是相邻的一层，但是不相连(左节点加入总和，右节点不加入总和，然后将右节点的子节点加入总和)
        // 获取二叉树的最大深度
        getDeep(root, 0);
        if (n == 1) {
            return root.val;
        }
        // 遍历
        int[] ans = dfs(root);
        return Math.max(ans[0], ans[1]);
    }

    public int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[2];
        }
        // 第二个元素为 root.left 的子节点的值
        int[] l = dfs(root.left);
        // 第二个元素为 root.right 的子节点的值
        int[] r = dfs(root.right);
        // 第一个元素为当前节点和左右子树的子节点之和，第二个节点为下层节点的最大值和
        // 即第一个元素表示偷取当前节点的最大值，第二个节点表示不偷取当前节点的最大值
        return new int[]{root.val + l[1] + r[1], Math.max(l[0], l[1]) + Math.max(r[0], r[1])};
    }

    public void getDeep(TreeNode root, int deep) {
        if (root == null) {
            n = Math.max(n, deep);
        } else {
            getDeep(root.left, deep + 1);
            getDeep(root.right, deep + 1);
        }
    }
}


// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
